package lc;

import java.util.*;

public class Q652 {

    Map<String, TreeNode> seen = new HashMap<String, TreeNode>();
    Set<TreeNode> repeat = new HashSet<TreeNode>();


    public List<TreeNode> findDuplicateSubtrees(TreeNode root) {
        dfs(root);
        return new ArrayList<>(repeat);
    }

    private String dfs(TreeNode treeNode) {
        if (treeNode == null) {
            return "";
        }
        String serial = treeNode.val +
                "(" +
                dfs(treeNode.left) +
                ")(" +
                dfs(treeNode.right) +
                ")";
        if (seen.containsKey(serial)) {
            repeat.add(seen.get(serial));
        } else {
            seen.put(serial, treeNode);
        }
        return serial;
    }


}
